package mo.leetcode_hot;

public class L208 {

    private L208[] children;
    private boolean end;

    public L208() {
        children = new L208[26];
        end = false;
    }

    public void insert(String word) {
        L208 node = this;
        for (char c : word.toCharArray()) {
            L208 child = node.children[c - 'a'];
            if (child == null) {
                child = new L208();
                node.children[c-'a'] = child;
            }
            node = child;
        }
        node.end = true;
    }

    public boolean search(String word) {
        L208 node = searchTrie(word);
        if (node == null || !node.end) {
            return false;
        }
        return true;
    }

    public boolean startsWith(String prefix) {
        return searchTrie(prefix) != null;
    }

    private L208 searchTrie(String word) {
        L208 node = this;
        for (char c : word.toCharArray()) {
            L208 child = node.children[c - 'a'];
            if (child == null) {
                return null;
            }
            node = child;
        }
        return node;
    }

}
